package com.desheng.bigdata.ds.heap;

import java.awt.*;

/*
    数据结构之堆--Heap

    如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不
使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就
令k等于2k或2k+1。

    每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个
子结点的顺序并没有做规定
 */
public class Heap<E extends Comparable<E>> {

    private int size;//堆的size
    private E[] items;

    public Heap(int capacity) {
        this.items = (E[])new Comparable[capacity + 1];
        size = 0;
    }

    /*
        判断索引i位置的元素是否小于索引j位置的元素
     */
    public boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }
    //交换索引i和索引j位置的元素
    public void exchange(int i, int j) {
        E tmp = items[i];
        items[i] = items[j];
        items[j] = tmp;
    }

    public void insert(E e) {
        if(size == items.length - 1) {
            E[] newItems = (E[])new Comparable[items.length + items.length / 2];
            System.arraycopy(items,1, newItems, 1, size);
            items = newItems;
        }
        items[++size] = e;
        swim(size);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k){
        //如果已经到了根结点，就不需要循环了
        while (k > 1) {
            //比较当前结点和其父结点
            if(less(k / 2, k)) {
                exchange(k / 2, k);
            }
            k = k / 2;
        }
    }
    //最大元素就是数组中的第一个元素
    public E delMax() {
        E maxVal = items[1];
        //交换最大元素索引和最后索引
        exchange(1, size);
        //将最后一个索引指向的元素删除，同时size--
        items[size--] = null;
        //进行节点的移动
        sink(1);
        return maxVal;
    }

    //使用sink算法，将k索引位置处的元素移动到堆中得正确的位置
    private void sink(int k) {
        //如果当前已经是最底层了，就不需要循环了
        while(2 * k <= size) {
            //找到子节点中较大的节点索引
            int max = -1;
            if(2 * k + 1 <= size) {
                if(less(2 * k, 2 * k + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                max = 2 * k;
            }
            //比较当前结点和子结点中的较大者，如果当前结点不小，则结束循环
            if(!less(k, max)) {
                break;
            }
            //和子节点中较大的节点进行交换
            exchange(k, max);
            //变化k的参数，进行下一次的比较
            k = max;
        }
    }

}
